#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+5;
template<typename T>void read(T &x){
    x=0;char c=getchar();int f=1;
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    x*=f;
}
struct Node{
    ll l,r,w;
}node[N],newnode[N];
bool cmp(Node a,Node b){
    return a.r<b.r;
}
ll T,n,cnt=0,maxn=0;
ll a[N],pos[N],dp[N],maxl[N];
void solve(){
    read(n);
    cnt=0;maxn=0;
    memset(pos,0,sizeof(pos));
    memset(dp,0,sizeof(dp));
    memset(maxl,0,sizeof(maxl));
    for(ll i=1;i<=n;i++){
        read(a[i]);
        if(pos[a[i]]) node[++cnt]=(Node){pos[a[i]],i,a[i]};
        pos[a[i]]=i;
    }
    sort(node+1,node+cnt+1,cmp);
    dp[1]=node[1].w;
//    dp[2]=node[1].w+node[2].w;
//    maxl[2]=max(node[1].l,node[2].l);
    for(ll i=2;i<=n;i++){
        for(ll j=i-1;j>=1;j--){
            if(node[i].l<maxl[j]&&node[i].l<node[j].r) continue;
            dp[i]=max(dp[i],node[i].w+dp[j]);
            maxl[i]=max(node[i].l,node[j].r);
            break;
        }
    }
    for(ll i=1;i<=cnt;i++) maxn=max(maxn,dp[i]);
    printf("%lld\n",maxn);
}
/*
ll T,n,cnt=0,newcnt=0,maxn=0,maxm=0,id=0;
ll a[N],pos[N],rt[N],dp[N],mem[N];
void solve(){
    cnt=0;maxn=0;
    memset(pos,0,sizeof(pos));
    read(n);
    for(ll i=1;i<=n;i++){
        read(a[i]);
        if(pos[a[i]]) node[++cnt]=(Node){pos[a[i]],i,a[i]};
        pos[a[i]]=i;
    }
    sort(node+1,node+cnt+1,cmp);
    for(ll i=1;i<=cnt;i++) rt[i]=node[i].r;
//    for(ll i=1;i<=cnt;i++) cout<<node[i].l<<' '<<node[i].r<<' '<<node[i].w<<'\n';
    for(ll i=1;i<=cnt;i++){
        ll p=upper_bound(rt+1,rt+i+1,node[i].l)-rt-1;
        mem[i]=p;
        dp[i]=dp[p]+node[i].w;
//        cout<<i<<' '<<p<<' '<<dp[i]<<endl;
    }
    for(ll i=1;i<=cnt;i++){
        if(dp[i]>maxn){
            maxn=dp[i];
            id=i;
        }
    }
//    cout<<maxn;
//    cout<<"id:"<<id<<' '<<mem[id]<<'\n';
    while(id){
        node[id].w=0;
        rt[id]=1e9;
        id=mem[id];
    }
    sort(rt+1,rt+cnt+1);
    newcnt=0;
    for(ll i=1;i<=cnt;i++){
        if(node[i].w==0) continue;
        newnode[++newcnt]=node[i];
    }
//   cout<<newcnt<<'\n';
    for(ll i=1;i<=newcnt;i++){
        ll p=upper_bound(rt+1,rt+i+1,newnode[i].l)-rt-1;
        dp[i]=dp[p]+newnode[i].w;
//        cout<<i<<' '<<p<<' '<<dp[i]<<endl;
    }
    maxm=0;
    for(ll i=1;i<=newcnt;i++){
        maxm=max(maxm,dp[i]);
    }
    printf("%lld\n",maxn+maxm);
}*/
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);

    read(T);
    while(T--) solve();
    return 0;
}
/*
1
8
3 5 2 5 1 2 1 4
*/
